home *** CD-ROM | disk | FTP | other *** search
- #include "demo5.h"
-
- /*
-
- Database of (routes between) cities and associated distances.
-
- */
-
- ROUTE_
- table[] = {
- { "amsterdam", "hamburg" ,440 },
- { "amsterdam", "londen", 550 },
- { "amsterdam", "brussel", 210 },
- { "amsterdam", "keulen", 250 },
- { "brussel", "frankfort", 410},
- { "brussel", "parijs", 560 },
- { "brussel", "londen", 390 },
- { "brussel", "luxemburg", 220},
- { "brussel", "keulen" , 220 },
- { "bordeaux", "madrid" ,690 },
- { "bordeaux", "marseille", 630 },
- { "keulen", "hamburg", 430 },
- { "keulen", "frankfort", 200},
- { "keulen", "luxemburg", 200},
- { "keulen", "basel", 480},
- { "parijs", "bordeaux", 560},
- { "parijs", "marseille", 770},
- { "parijs", "luxemburg", 340},
- { "parijs", "basel", 490},
- { "madrid", "lissabon", 650},
- { "marseille", "genua", 400},
- { "marseille", "bern", 580},
- { "frankfort", "basel", 330},
- { "frankfort", "hamburg", 490},
- { "frankfort", "berlijn", 530},
- { "frankfort", "wenen", 720},
- { "bern", "basel", 90},
- { "bern", "milaan", 350},
- { "bern", "genua", 490},
- { "boedapest", "wenen", 250},
- { "triest", "wenen", 500},
- { "triest", "milaan", 420},
- { "triest", "frankfort", 900},
- { "milaan", "rome", 590},
- { "hamburg", "kopenhagen", 320},
- { "genua", "rome", 540},
- { "genua", "milaan", 140},
- { "palermo", "rome", 590},
- { "wenen", "basel", 840},
- { "wenen", "berlijn", 660},
- { "wenen", "warschau", 690},
- { "berlijn", "hamburg", 290},
- { "berlijn", "amsterdam", 660},
- { "berlijn", "warschau", 560},
- { "luxemburg", "frankfort", 230},
- { "luxemburg", "basel", 330},
- { NULL, NULL, 0} // marks end of table
- };
-
-
-
-
- PATH_::PATH_(CITY_ *start, CITY_ *target)
- :UNICOST_GRAPH_(start, target, 0)
- {
- }
-
-
-
- CITY_::CITY_(const char *p, int d)
- {
- city = p;
- dist = d;
- }
-
-
-
- /* DISPLAY
-
- Displays current city and distance of the path so far.
-
- */
-
-
- void CITY_::display() const
- {
- printf("%15s %5d\n", city, get_g());
- }
-
-
-
- int CITY_::equal(const VOBJECT_ &other) const
- {
- return(!strcmp(city, ((const CITY_ &)other).getcity()));
- }
-
-
-
- const char *CITY_::getcity() const
- {
- return(city);
- }
-
-
-
- int CITY_::getdist() const
- {
- return(dist);
- }
-
-
-
- /* EXPAND
-
- This function expands the current node by generating all of
- its successor nodes. In this case this means we build a linked
- list of all the cities that are directly reachable from the
- current city. We just scan the database of cities for a match,
- since a city may be in either half of an entry (from A to B ==
- from B to A) we need to check both halves.
-
- */
-
- NODE_ *CITY_::expand(int ) const
- {
- int
- i;
- CITY_
- *start = NULL,
- *tmp;
-
- for (i = 0; table[i].from != NULL; i++)
- {
- if (!strcmp(table[i].from, city)) // found city in first halt of entry
- tmp = new CITY_(table[i].to, table[i].distance);
- else if (!strcmp(table[i].to, city)) // found city in 2nd half of entry
- tmp = new CITY_(table[i].from, table[i].distance);
- else
- continue; // no match
-
- // found a match
- tmp->setnext(start); // builds a linked list
- start = tmp;
- }
- return(start);
- }
-
-
-
- /* COMPUT_G
-
- Function compute_g() serves to compute the cost of getting from
- the parent node to the current node. In this case the cost is
- represented by the distance of the path from the 'parent' city the
- current city, so we just return the distance associated with the city.
-
- */
-
- int PATH_::compute_g(const NODE_ &node)
- {
- return(((const CITY_ &)node).getdist());
- }
-
-
-
- int main()
- {
- PATH_
- path(new CITY_("kopenhagen", 0), new CITY_("rome", 0));
-
- path.generate();
- return(1);
- }
-